﻿// 0813train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>
#include <limits>

using namespace std;

/*
 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
示例 1：
输入：x = 4
输出：2

示例 2：
输入：x = 8
输出：2
 */
int solve01(int x)
{
    int result = -1;
    int left = 0;
    int right = x;

    while (left<=right)
    {
        int mid = left + (right - left) / 2;
        if ((long)mid*mid<=x)
        {
            result = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }

    }
    return result;
    //solve01
}


/*
n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来
吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根
如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4

示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30

示例 3：
输入：piles = [30,11,23,4,20], h = 6
输出：23
 */
long long CalculateSpeed(vector<int>& piles, int speed)
{
    if (speed == 0) return INT_MAX;

    long long total = 0;
    for (auto&amount:piles)
    {
        long long tmp = ceil(static_cast<double>(amount) / speed);
        total += tmp;
    }
    return total;
}

int solve02(vector<int>& piles, int h)
{
    sort(piles.begin(), piles.end());
    int left = 0, right = piles[piles.size() - 1];

    int result = INT_MAX;
    while (left<right)
    {
        int mid = left + (right - left) / 2;
        long long need_time = CalculateSpeed(piles, mid);
        //cout << "mid " << mid << endl;
        //cout << "need_time " << need_time << endl;
        //cout << "------" << endl;
	    if (need_time <=h)
	    {
            result = min(result,mid);
            right = mid;
	    }
        else
        {
            left = mid + 1;
        }
    }

    if (result == INT_MAX)
    {
        result = piles[piles.size() - 1];
    }

    return result;
    //solve02
}


/*
 有 N 个容量一样的小桶等距排开，且每个小桶都默认装了数量不等的小球，
 每个小桶装的小球数量记录在数组bucketBallNums中，
 游戏开始时，要求所有桶的小球总数不能超过SUM，
 如果小球总数超过SUM，则需对所有的小桶统一设置一个尽可能大的容量最大值maxCapacity，
 并需将超过容量最大值的小球拿出来，直至所有小桶里的小球数量均不大于maxCapacity。

限制规则一
如果所有小桶的小球总和小于SUM，则无需设置容量值，并且无需从小桶中拿球出来，返回结果[]

限制规则二
如果所有小桶的小球总和大于SUM，则需设置一个尽可能大的容量最大值maxCapacity，
并且需从小桶中拿球出来，返回从每个小桶拿出的小球数量组成的数组
输入
第一行输入2个正整数，数字之间使用空格隔开，其中第一个数字表示SUM，第二个数字表示bucketBallNums数组长度；
第二行输入N个正整数，数字之间使用空格隔开，表示bucketBallNums的每一项。
输出
一个数组。

示例1
输入
14 7
2 3 2 5 5 1 4
输出
[0, 1, 0, 3, 3, 0, 2]

小球总数为22，SUM = 14，超出范围了，需从小桶取球。
- maxCapacity = 1，取出球后，1 1 1 1 1 1 1， 桶里剩余小球总和为7，远小于14
- maxCapacity = 2，取出球后，2 2 2 2 2 1 2，桶里剩余小球总和为13，小于14
- maxCapacity = 3，取出球后，2 3 2 3 3 1 3，桶里剩余小球总和为16，大于14
因此选择maxCapacity为2 ，每个小桶小球数量大于 2 的都需要拿出来。

目标，设置一个maxCapacity，使得每个小桶内的球小于maxCapacity，并且总和不超过SUM
返回值，返回从每个小桶拿出的小球数量组成的数组
 */

long long CalculateSum03(vector<int>&oh_vec, int limit_num)
{
    long long result = 0;
    if (limit_num==-1)
    {
        for (auto& num : oh_vec)
        {
            result += num;
        }
        return result;
    }

    for (auto&num: oh_vec)
    {
        if (num<= limit_num)
        {
            result += num;
            continue;
        }
        result += limit_num;
    }
    return result;
	//CalculateSum03
}

void solve03(vector<int>& origin_vec, int target)
{
    //复制一份，防止排序打乱原数组次序
    vector<int>oh_vec = origin_vec;
    long long curr_sum = CalculateSum03(oh_vec, -1);
    if (curr_sum<=target)
    {
        cout << "[]";
        return;
    }

    sort(oh_vec.begin(), oh_vec.end());
    int vec_size = oh_vec.size();
    int left = 0, right = oh_vec[vec_size-1];

    int result = 0;
    while (left<right)
    {
        int mid = left + (right - left) / 2;
        //cout << mid << endl;
        if (CalculateSum03(oh_vec, mid)<=target)
        {
            //<=都有可能是正确答案
            result = max(result, mid);
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    //cout << result;
    vector<int>result_vec;
    for (auto&num:origin_vec)
    {
        if (num<result)
        {
            //小于不需要丢
            result_vec.push_back(0);
        }
        else
        {
            result_vec.push_back(num - result);
        }
    }

    cout << '[';
    for (int i=0; i<vec_size; i++)
    {
	    if (i!=vec_size-1)
	    {
            cout << result_vec[i] << ',' << ' ';
	    }
        else
        {
            cout << result_vec[i];
        }
    }

    cout << ']';
    //solve03
}


int main()
{
	{
        //14 7
        //2 3 2 5 5 1 4
		//3632432 19
		//4208628 8323103 7137652 520602 3147469 9721483 8332276 5947244 1665467 1355879 9609078 6521925 7229896 2010691 2235705 1774359 7503493 7115621 7560421
        //int target = 3632432;
        //vector<int>oh_vec = { 4208628,8323103,7137652,520602,3147469,9721483,
        //	8332276,5947244,1665467,1355879,9609078,6521925,7229896,2010691,2235705,
        //	1774359,7503493,7115621,7560421 };
        //3 3
		//1 2 3

        int target, vec_size;
        cin >> target >> vec_size;
        vector<int>oh_vec(vec_size);
        for (int i=0; i<vec_size; i++)
        {
            cin >> oh_vec[i];
        }

        //for (auto&num:oh_vec)
        //{
        //    cout << num << ' ';
        //}

        solve03(oh_vec, target);
        //cout << CalculateSum03(oh_vec, 1);

        return 0;
	}

    //piles = [3,6,7,11], h = 8  4
    //piles = [30,11,23,4,20], h = 5  30
    //piles = [30,11,23,4,20], h = 6 23
    vector<int>piles = { 3,6,7,11 };
    int h = 8;
    cout << solve02(piles, h);

    //cout << solve01(8);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
